МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
/
Звіт
до лабораторної роботи № 2
з курсу: «Методи синтезу та оптимізації»
на тему:
«Дослідження роботи методів лінійного програмування»
Мета роботи: вивчити основні алгоритми розв’язку задач лінійної оптимізації: розв'язати дану задачу ЛП використовуючи симплекс метод.
1.Короткі теоретичні відомості:
Задачі оптимізації, в яких цільова функція є лінійною функцією незалежних змінних (тобто має вигляд z = c1 x1+ c2 x2+...+ cn xn, де c1, c2,..., cn - константи, x1, x2,..., xn - змінні, n-довільне натуральне число) і умови, які визначають допустимі значення цих змінних мають вигляд лінійних рівнянь і нерівностей, відносять до задач лінійного програмування.
Лінійне програмування було розвинене в зв'язку із задачами економіки, з пошуком способів оптимального рішення і з використанням обмежених ресурсів. Розвиток і ускладнення економічних процесів, обчислювальної техніки стимулює широке використання математичних методів в управлінні, сприяє зростанню ролі лінійного програмування як одного з актуальних розділів прикладної математики.
Перед застосуванням симплекс-методу необхідною умовою є запис оптимізаційних задач в стандартній (канонічній) формі. Канонічна форма запису оптимізацій них задач передбачає, що:
усі змінні мають бути не від’ємними;
нерівності слід перетворити в рівності;
праві частини рівнянь мають бути не від’ємними.
Алгоритм симплекс-методу включає наступні процедури:
Крок 0. Використовуючи лінійну модель стандартної форми, визначається початкове допустиме базисне рішення шляхом прирівнювання до нуля небазисних n-m змінних.
Крок 1. З числа поточних небазисних (рівних нулю) змінних вибирається змінну, яка буде включена в новий базис і збільшення якої забезпечує поліпшення значення цільової функції. Якщо такої змінної немає, то обчислення припиняються, оскільки поточне базисне рішення оптимальне. В іншому випадку здійснюється перехід до кроку 2.
Крок 2. З числа змінних поточного базису вибирається змінна, яка виводиться зі списку базисних змінних і має прийняти нульове значення (стати небазисною) при введенні до складу базисних нової змінної.
Крок 3. Знаходиться нове базисне рішення, відповідне новим складам небазисних і базисних змінних. Здійснюється перехід до кроку 1.
2.Індивідуальне завдання:
13. Продукція може виготовлятися на будь-якому з трьох видів обладнання А, В, С. Трудоємкості (нормо-год.) і собівартість (у.о.) виробництва центнера продукції на цьому обладнанні виражаються відповідно числами 10, 9, 12 і 20, 17, 22. Скільки центнерів продукції потрібно виготовляти на кожному з видів обладнання, щоб сумарна собівартість продукції була б мінімальною, при умові, що сумарна трудомісткість не має перевищувати 660 нормо-год, а загальна кількість продукції не має бути менше 70 ц.?
3.Результат виконання:
F(X) = 20x1 + 17x2 + 22x3
x1 + x2 + x3≥70
10x1 + 9x2 + 12x3≤660
Запишемо систему в канонічному вигляді, ввівши додаткові змінні x4 , x5 , x6 :
1x1 + 1x2 + 1x3-1x4 + 0x5 + 1x6 = 70
10x1 + 9x2 + 12x3 + 0x4 + 1x5 + 0x6 = 660
Функцію мети запишемо так:
F(X) = 20x1+17x2+22x3+Mx6 → min
З рівнянь отримуємо:
x6 = 70-x1-x2-x3+x4 і
F(X) = 20x1 + 17x2 + 22x3 + M(70-x1-x2-x3+x4) → min
F(X) = (20-M)x1+(17-M)x2+(22-M)x3+(M)x4+(70M) → min
Отримана матриця коефіцієнтів:
Розв’яжемо систему рівнянь відносно базових змінних: x5, x6 ; взявши вільні змінні = 0 , отримаємо :
X1 = (0,0,0,0,660,70)
Базис
B
x1
x2
x3
x4
x5
x6
x6
70
1
1
1
-1
0
1
x5
660
10
9
12
0
1
0
F(X0)
70M
-20+M
-17+M
-22+M
-M
0
0
Оскільки базисне рішення негативне, переходимо до основного алгоритму:
Ітерація 1.
1. Перевірка на критерій оптимальності:
Даний опорний план неоптимальний, оскільки в індесному рядку знаходяться позитивні коефіцієнти.
2. Визначення нової базисної змінної
Новою базисною змінною виберемо стовпець з x2 , оскільки це найбільший елемент.
3. Визначення нової вільної змінної:
Вираховуємо значення...
